// @algorithm @lc id=100308 lang=typescript
// @title zi-fu-chuan-de-pai-lie-lcof
// @test("abc")
function permutation(s: string): string[] {
  const arr = s.split('');
  const ans: Set<string> = new Set();

  const backtrack = (arr: string[], idx: number) => {
    if (idx === arr.length) {
      ans.add(arr.join(''));
      return;
    }
    for (let i = idx; i < arr.length; i++) {
      [arr[i], arr[idx]] = [arr[idx], arr[i]];
      backtrack(arr, idx + 1);
      [arr[i], arr[idx]] = [arr[idx], arr[i]];
    }
  };

  backtrack(arr, 0);

  return [...ans];
}
